// easy

// 给定一个非空的字符串s
// 要求：检查该字符串s是否可以通过由它的一个子串重复多次构成

// 思路： KMP算法
// KMP算法的next数组来解决，next[j]表示的含义是：记录下标j之前（包括j）的模式串p中，最长相等前后缀的长度

// 如果整个模式串p的最长相等前后缀长度不为0，即next[p.length - 1] !== 0, 则说明整个模式串p中有最长相同前后缀，
// 假设next[p.length - 1] === k,则说明p[0:k] === p[m - k, m]
// 如果最长相等的前后缀是重叠的
//   我们去除字符串中相同的前后缀的重叠部分，剩下两头前后缀部分，然后再去除剩余的后缀部分，只保留剩余的前缀部分
//   如果整个字符串可以通过子串重复构成的话，那么这部分就是最小周期的子串
//      我们只需要判断整个子串的长度是否是剩余部分长度的整数倍即可，也就是判断 p.length % (p.length - next[size - 1]) === 0是否成立，如果成立
//      则字符串s可由s[0: p.length - next[size - 1]]构成的子串重复构成
// 如果最长相等的前后缀是不重叠的，那我们可以将重叠部分视为长度为0的空串，则剩余的部分就是去除后缀部分的剩余部分

function repeatedSubstringPattern(s) {
    let size = s.length
    if (size === 0) {
        return false
    }
    let next = generateNext(s)
    if (next[size - 1] !== 0 && size % (size - next[size - 1]) === 0) {
        return true
    }
    return false
} 

function generateNext(p) {
    let m = p.length
    let next = new Array(m).fill(0)
    let left = 0
    let right = 1
    while (right < m) {
        while (left > 0 && p[left] !== p[right]) {
            left = next[left - 1]
        }
        if (p[left] === p[right]) {
            left += 1
        }
        next[right] = left
        right += 1
    }
    return next
}

// let s = "abcabcabcabc"
let s = "aacaacaac"
console.log(repeatedSubstringPattern(s));

/**
 * next数组不减1
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    if(!needle.length) {
        return 0
    }
    let size = haystack.length
    let next = getNext(needle)
    let j = 0
    for(let i = 0; i < size; i++) {
        while( j > 0 && haystack[i] !== needle[j]) {
            j = next[j - 1]
        }
        if(needle[j] === haystack[i]) {
            j++
        }
        if(j === size) {
            return (i - needle.length + 1)
        }
    }
    return -1
};

function getNext(needle) {
    let size = needle.length
    let next = new Array(size).fill(0)
    let left = 0
    let right = 1
    while (right < size) {
        if (left > 0 && needle[left] !== needle[right]) {
            left = next[left - 1]
        }
        if (needle[left] === needle[right]) {
            left++
        }
        next[right] = left
        right++
    }
    return next
}

// strStr('sadbutsad', 'sad')
strStr('sadbutsad', 'sad')